package leetcode;

import java.util.Stack;

/**
 * Created by Ghost on 2015/1/18 0018.
 */
class BinarySearchTreeIterator{
    private TreeNode current;
    private Stack<TreeNode> treeNodeStack;
    public BinarySearchTreeIterator(TreeNode root){
        current = root;
        treeNodeStack = new Stack<TreeNode>();
    }

    public boolean hasNext(){
        return !treeNodeStack.isEmpty() || !(current==null);
    }

    public int next(){
        while(current!=null){
            treeNodeStack.push(current);
            current = current.left;
        }

        TreeNode rst = treeNodeStack.pop();
        current = rst.right;
        return rst.val;
    }
}
public class Binary_Search_Tree_Iterator {
    private TreeNode Root;
    private TreeNode current;
    private int max;
    public Binary_Search_Tree_Iterator(TreeNode root) {
        Root = root;
        current = null;
        TreeNode tmp = root;
        while(tmp!=null){
            max = tmp.val;
            tmp = tmp.right;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(Root==null)
            return false;
        return current == null || current.val < max;
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode tmp = Root;
        TreeNode pre = null;
        TreeNode rst = null;
        TreeNode backup = null;
        while(tmp!=current){
            if(current==null){
                pre = tmp;
                tmp = tmp.left;
            } else{
                if(current.val<tmp.val){
                    pre = tmp;
                    backup = tmp;
                    tmp = tmp.left;
                } else if(current.val>tmp.val){
                    if(backup==null || pre==null){
                        if(backup==null)
                            backup = tmp;
                        if(pre == null)
                            pre=tmp;
                    }
                    else
                        backup = pre.val<backup.val?backup:pre;
                    pre = tmp;
                    tmp = tmp.right;
                }
            }

        }

        if(current==null){
            current = pre;
            return current.val;
        }
        else{
            if(tmp.right==null){
                rst = backup;
            }
            else{
                tmp = tmp.right;
                while(tmp.left!=null)
                    tmp = tmp.left;
                rst = tmp;
            }
            current = rst;
            return rst.val;
        }
    }

    public static void main(String[] args){
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(2);
        root.left.left.left = new TreeNode(1);
        root.left.left.right = new TreeNode(3);
        root.left.right = new TreeNode(6);
        root.left.right.left = new TreeNode(5);
        root.left.right.right = new TreeNode(7);

        root.right = new TreeNode(12);
        root.right.left = new TreeNode(10);
        root.right.left.left = new TreeNode(9);
        root.right.left.right = new TreeNode(11);

        root.right.right = new TreeNode(14);
        root.right.right.left = new TreeNode(13);
        root.right.right.right = new TreeNode(15);

//        Binary_Search_Tree_Iterator binary_search_tree_iterator = new Binary_Search_Tree_Iterator(root);
        BinarySearchTreeIterator binary_search_tree_iterator = new BinarySearchTreeIterator(root);
        while(binary_search_tree_iterator.hasNext()){
            System.out.println(binary_search_tree_iterator.next());
        }
    }
}
